import { cloneDeep } from "lodash"



export const sort = (arr: number[], left: number, right: number) => {
    if (left >= right) {
        return
    }

    const mid = Math.floor((left + right) / 2)

    sort(arr, left, mid)
    sort(arr, mid + 1, right)
    mergeSort(arr, left, right, mid)
}

const mergeSort = (arr: number[], left: number, right: number, mid: number) => {

    let tmpArr = cloneDeep(arr.slice(left, right + 1))

    // 归并数组的左起点和右起点
    let i = left, j = mid + 1

    for (let k = left; k <= right; k++) {
        if (i > mid) {
            // 如果左边越界
            arr[k] = tmpArr[j - left]
            j++
        } else if (j > right) {
            // 如果右边越界
            arr[k] = tmpArr[i - left]
            i++
        } else if (tmpArr[i - left] <= tmpArr[j - left]) {
            arr[k] = tmpArr[i - left]
            i++
        } else {
            arr[k] = tmpArr[j - left]
            j++
        }
    }
}